package 搜索;

import java.util.Arrays;

/**
 * 在一个8*8的棋盘上，摆放8个皇后
 * 皇后之间不能相互攻击：
 * 任意两个皇后都不能在同一行，同一列，或同一斜线上
 * 最多有多少种解法
 */
public class 八皇后问题 {

    // 最多多少个皇后
    int max = 8;

    // 选择皇后的过程存储
    int[] array = new int[max];

    int ans = 0;

    public static void main(String[] args) {

        八皇后问题 queue8 = new 八皇后问题();
        queue8.check(0);
        System.out.println(queue8.ans);

    }

    /**
     * 放置第row行的皇后
     * 思路：
     * 判断索引n行某列的皇后，是否和前面n-1个皇后冲突，如果不冲突
     * 则继续放置n+1行的皇后的所有可能性
     */
    private void check(int row) {
        if (row == max) {  // n=8，其实8个换后就已经放好
            print();
            ans++;
            return;
        }

        // 依赖放入皇后，并判断是否冲突
        for (int column = 0; column < max; column++) {
            array[row] = column;
            if (judge(row)) {  //第row行，column列放置皇后不冲突
                // 接着放下一行的皇后，开始递归
                check(row + 1);
            }
            // 如果冲突，开始本行的下一列
        }

    }


    /**
     * 判断第索引n个皇后，是否和前面n-1个皇后冲突
     */
    public boolean judge(int curRow) {
        // 注意：只需要判断当前行和之前行的皇后是否冲突
        for (int preRow = 0; preRow < curRow; preRow++) {
            // 同一列冲突
            if (array[preRow] == array[curRow]) {
                return false;
            }
            // 同一斜线冲突，45度的斜率=1或-1
            if (Math.abs(curRow - preRow) == Math.abs(array[curRow] - array[preRow])) {
                return false;
            }
        }
        return true;
    }

    public void print() {
        System.out.println(Arrays.toString(array));
    }

}
